
//3604.有向图中到达终点的最少时间
class Solution {
public:
    int minTime(int n, vector<vector<int>>& edges) {
        //依旧是Dijkstra算法
        //此题是稀疏图,所以使用优先级队列来实现,时间复度更小
        //1. 先存储每个位置之间的关系
        vector<vector<tuple<int,int,int>>> path(n);   //使用tuple来存储数据,因为要存储:到达的位置,起始时间,结束时间
        for(auto& nums : edges)
        {
            int x = nums[0], y = nums[1] ,start = nums[2] ,end = nums[3];
            path[x].emplace_back(y,start,end);
        }

        //2. 开始准备进行循环 
        vector<int> dis(n,INT_MAX);             //记录到达每个位置的最小时间·
        vector<int> vist(n);                    //记录哪些位置已经作为扩展的起始位置了
        priority_queue<pair<int,int> ,vector<pair<int,int>>,greater<pair<int,int>>> pq;     //记录每个位置的时间 
        pq.push({0,0});
        vist[0] = 1;
        while(pq.size())
        {
            auto [clock,pos] = pq.top();
            pq.pop();
            if(dis[pos] < clock) continue;
            dis[pos] = clock;
            vist[pos] = 1;
            for(auto& [next,start,end] : path[pos])
            {
                if(clock < start ) pq.push({start + 1 ,next});                      //时间不够,要加时间才能入队列
                else if(clock >= start && clock <= end) pq.push({clock+1 ,next});   //时间够,直接去下一个位置
            }
        }
        return dis[n-1]==INT_MAX?-1:dis[n-1];
    }
};